package hot100;


/*
 * Author：江松
 * Date：2023/4/8 14:03
 *
 和为k的子数组：
 1，感觉得用分治

 2,暴力枚举：枚举所有区间然后求和O(n^3)，可以优化枚举终点，然后从后往前算O(n^2),也可以使用前缀和优化

 3,前缀和+哈希表优化：
 <前缀和，出现次数>
 每次遇到加上sum-k的次数
 */

import java.util.HashMap;

public class Main560 {


    public int subarraySum(int[]nums,int k){
        int n=nums.length;
        //前缀和---出现次数
        HashMap<Integer,Integer>map=new HashMap<>();
        map.put(0,1);
        int sum=0;
        int res=0;
        for(int i=0;i<n;++i){
            sum+=nums[i];
            if(map.containsKey(sum-k)){
                res+=map.get(sum-k);
            }
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        return res;
    }

    //前缀和
    public int subarraySum2(int[] nums, int k) {
        int n=nums.length;
        int res=0;
        int sum[]=new int[n];
        for(int i=1;i<=n;++i){
            sum[i]=sum[i-1]+nums[i-1];
        }


        for(int i=1;i<=n;++i){
            for(int j=i;j<=n;++j){
                if(sum[j]-sum[i-1]==k){
                    res++;
                }
            }
        }
        return res;
    }



    /*
        public int subarraySum(int[] nums, int k) {
        int n=nums.length;
        int res=0;
        //枚举终点
        for(int i=0;i<n;++i){
            int sum=0;
            //从后向前枚举并求和
            for(int j=i;j>=0;--j){
                sum+=nums[j];
                if(sum==k){
                  res++;
                }
            }
        }
        return res;
    }
     */

    /*
    public int merge(int l,int r,int nums[],int k){
        if(l>=r)return nums[l]==k?1:0;

        int res=0;
        int mid=l+r>>1;
        //分别加上左右两边的连续子数组个数
        res+=merge(l,mid,nums,k)+merge(mid+1,r,nums,k);
        //横跨左右
        int i=mid,j=mid+1;
        int sum=0;
        boolean op=true;//交替相加
        while(i>=l&&j<=r){
            //System.out.printf("sum:%d res:%d (%d,%d)\n",sum,res,i,j);
            if(sum==k){
                res++;
            }
            if(op){
                sum+=nums[i--];
                op=false;
            }else {
                sum+=nums[j++];
                op=true;
            }
        }
        while(i>=l){
            if(sum==k)res++;
            sum+=nums[i--];
        }
        while(j<=r){
            if(sum==k)res++;
            sum+=nums[j++];
        }
        return res;
    }

    public int subarraySum(int[] nums, int k) {
        return merge(0,nums.length-1,nums,k);
    }
    */


    public static void main(String[] args) {
        int nums[]={1,1,1};
        int k=2;
        System.out.println(new Main560().subarraySum(nums,k));
    }
}
